/*
 * 0167. 链表求和
 * 你有两个用链表代表的整数，其中每个节点包含一个数字。数字存储按照在原来整数中相反的顺序，使得第一个数字位于链表的开头。写出一个函数将两个整数相加，用链表形式返回和。
 * https://www.lintcode.com/problem/add-two-numbers/description
 * 
 * 样例
 * 给出两个链表 3->1->5->null 和 5->9->2->null，返回 8->0->8->null
 * 
 * 2018.06.25 @jeyming
 */
package add_two_numbers_0167;

import java.util.ArrayList;
import java.util.List;

//Definition for ListNode
class ListNode {
	int val;
	ListNode next;
	ListNode(int x) {
		val = x;
		next = null;
	}
}

public class Add_two_numbers_0167 {
	/**
	 * @param l1: the first list
	 * @param l2: the second list
	 * @return: the sum list of l1 and l2 
	 */
	public ListNode addLists(ListNode l1, ListNode l2) {
		// write your code here
		ListNode p = l1;
		ListNode q = l2;
		List<Integer> list = new ArrayList<Integer>();
		int num = 0;
		while((p != null) || (q != null) || (num > 0)) {
			if((p == null) && (q != null)) {
				num += q.val;
				q = q.next;
			} else if((q == null) && (p != null)) {
				num += p.val;
				p = p.next;
			} else if((p != null) && (q != null)) {
				num += (p.val + q.val);
				p = p.next;
				q = q.next;
			}
			list.add(num % 10);
			num /= 10;
		}
		ListNode head = new ListNode(list.get(0));
		p = head;
		for(int i = 1; i < list.size(); ++i) {
			ListNode node = new ListNode(list.get(i));
			p.next = node;
			p = p.next;
		}
		return head;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
